{\rtf1\adeflang1025\ansi\ansicpg936\uc2\adeff0\deff0\stshfdbch0\stshfloch0\stshfhich0\stshfbi0\deflang1033\deflangfe2052{\fonttbl{\f0\froman\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\f1\fswiss\fcharset0\fprq2{\*\panose 020b0604020202020204}Arial;}
{\f2\fmodern\fcharset0\fprq1{\*\panose 02070309020205020404}Courier New;}{\f36\froman\fcharset238\fprq2 Times New Roman CE;}{\f37\froman\fcharset204\fprq2 Times New Roman Cyr;}{\f39\froman\fcharset161\fprq2 Times New Roman Greek;}
{\f40\froman\fcharset162\fprq2 Times New Roman Tur;}{\f41\fbidi \froman\fcharset177\fprq2 Times New Roman (Hebrew);}{\f42\fbidi \froman\fcharset178\fprq2 Times New Roman (Arabic);}{\f43\froman\fcharset186\fprq2 Times New Roman Baltic;}
{\f44\froman\fcharset163\fprq2 Times New Roman (Vietnamese);}{\f46\fswiss\fcharset238\fprq2 Arial CE;}{\f47\fswiss\fcharset204\fprq2 Arial Cyr;}{\f49\fswiss\fcharset161\fprq2 Arial Greek;}{\f50\fswiss\fcharset162\fprq2 Arial Tur;}
{\f51\fbidi \fswiss\fcharset177\fprq2 Arial (Hebrew);}{\f52\fbidi \fswiss\fcharset178\fprq2 Arial (Arabic);}{\f53\fswiss\fcharset186\fprq2 Arial Baltic;}{\f54\fswiss\fcharset163\fprq2 Arial (Vietnamese);}{\f56\fmodern\fcharset238\fprq1 Courier New CE;}
{\f57\fmodern\fcharset204\fprq1 Courier New Cyr;}{\f59\fmodern\fcharset161\fprq1 Courier New Greek;}{\f60\fmodern\fcharset162\fprq1 Courier New Tur;}{\f61\fbidi \fmodern\fcharset177\fprq1 Courier New (Hebrew);}
{\f62\fbidi \fmodern\fcharset178\fprq1 Courier New (Arabic);}{\f63\fmodern\fcharset186\fprq1 Courier New Baltic;}{\f64\fmodern\fcharset163\fprq1 Courier New (Vietnamese);}}{\colortbl;\red0\green0\blue0;\red0\green0\blue255;\red0\green255\blue255;
\red0\green255\blue0;\red255\green0\blue255;\red255\green0\blue0;\red255\green255\blue0;\red255\green255\blue255;\red0\green0\blue128;\red0\green128\blue128;\red0\green128\blue0;\red128\green0\blue128;\red128\green0\blue0;\red128\green128\blue0;
\red128\green128\blue128;\red192\green192\blue192;}{\stylesheet{\ql \li0\ri0\widctlpar\wrapdefault\aspalpha\aspnum\faauto\adjustright\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24\alang1025 \ltrch\fcs0 \fs24\lang1033\langfe1033\cgrid\langnp1033\langfenp1033 
\snext0 Normal;}{\*\cs10 \additive \ssemihidden Default Paragraph Font;}{\*
\ts11\tsrowd\trftsWidthB3\trpaddl108\trpaddr108\trpaddfl3\trpaddft3\trpaddfb3\trpaddfr3\trcbpat1\trcfpat1\tblind0\tblindtype3\tscellwidthfts0\tsvertalt\tsbrdrt\tsbrdrl\tsbrdrb\tsbrdrr\tsbrdrdgl\tsbrdrdgr\tsbrdrh\tsbrdrv 
\ql \li0\ri0\widctlpar\wrapdefault\aspalpha\aspnum\faauto\adjustright\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\langnp1024\langfenp1024 \snext11 \ssemihidden Normal Table;}{\*\cs15 \additive \rtlch\fcs1 \af0 
\ltrch\fcs0 \ul\cf2 \sbasedon10 \styrsid9191485 Hyperlink;}}{\*\latentstyles\lsdstimax156\lsdlockeddef0}{\*\rsidtbl \rsid7031373\rsid7090704\rsid7759697\rsid9191485\rsid9271887\rsid13638427\rsid14694867\rsid14842497\rsid16145397}{\*\generator Microsoft Wo
rd 11.0.0000;}{\info{\author John Hargrove}{\operator \'ce\'a2\'c8\'ed\'d3\'c3\'bb\'a7}{\creatim\yr2007\mo2\dy10\hr17\min39}{\revtim\yr2009\mo4\dy8\hr14\min34}{\version7}{\edmins183}{\nofpages6}{\nofwords1218}{\nofchars6945}
{\*\company Microsoft Corporation}{\nofcharsws8147}{\vern24613}{\*\password 00000000}}{\*\xmlnstbl {\xmlns1 http://schemas.microsoft.com/office/word/2003/wordml}{\xmlns2 urn:schemas-microsoft-com:office:smarttags}}
\paperw12240\paperh15840\margl1800\margr1800\margt1440\margb1440\gutter0\ltrsect 
\ftnbj\aenddoc\donotembedsysfont0\donotembedlingdata1\grfdocevents0\validatexml0\showplaceholdtext0\ignoremixedcontent0\saveinvalidxml0\showxmlerrors0\noxlattoyen\expshrtn\noultrlspc\dntblnsbdb\nospaceforul\hyphcaps0\horzdoc\dghspace120\dgvspace120
\dghorigin1701\dgvorigin1984\dghshow0\dgvshow3\jcompress\viewkind4\viewscale170\nolnhtadjtbl\rsidroot14694867 \fet0{\*\wgrffmtfilter 013f}\ilfomacatclnup0\ltrpar \sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\*\pnseclvl1\pnucrm\pnstart1\pnindent720\pnhang 
{\pntxta \dbch .}}{\*\pnseclvl2\pnucltr\pnstart1\pnindent720\pnhang {\pntxta \dbch .}}{\*\pnseclvl3\pndec\pnstart1\pnindent720\pnhang {\pntxta \dbch .}}{\*\pnseclvl4\pnlcltr\pnstart1\pnindent720\pnhang {\pntxta \dbch )}}{\*\pnseclvl5
\pndec\pnstart1\pnindent720\pnhang {\pntxtb \dbch (}{\pntxta \dbch )}}{\*\pnseclvl6\pnlcltr\pnstart1\pnindent720\pnhang {\pntxtb \dbch (}{\pntxta \dbch )}}{\*\pnseclvl7\pnlcrm\pnstart1\pnindent720\pnhang {\pntxtb \dbch (}{\pntxta \dbch )}}{\*\pnseclvl8
\pnlcltr\pnstart1\pnindent720\pnhang {\pntxtb \dbch (}{\pntxta \dbch )}}{\*\pnseclvl9\pnlcrm\pnstart1\pnindent720\pnhang {\pntxtb \dbch (}{\pntxta \dbch )}}\pard\plain \ltrpar\ql \li0\ri0\nowidctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 
\af0\afs24\alang1025 \ltrch\fcs0 \fs24\lang1033\langfe1033\cgrid\langnp1033\langfenp1033 {\rtlch\fcs1 \af1\afs48 \ltrch\fcs0 \f1\fs48\insrsid9191485 The AVL Tree Rotations Tutorial}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par }{\rtlch\fcs1 \af1\afs16 \ltrch\fcs0 \f1\fs16\insrsid9191485 By John Hargrove
\par }{\rtlch\fcs1 \af1\afs16 \ltrch\fcs0 \f1\fs16\insrsid13638427 Version 1.0.1, Updated Mar-22-2007}{\rtlch\fcs1 \af1\afs16 \ltrch\fcs0 \f1\fs16\insrsid9191485 
\par }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par }{\rtlch\fcs1 \af1\afs36 \ltrch\fcs0 \f1\fs36\insrsid9191485 Abstract
\par }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
I wrote this document in an effort to cover what I consider to be a dark area of the AVL Tree concept.  When presented with the task of writing an AVL tree class in Java, I was left scouring the web for useful information on how this all works.  There was
 
a lot of useful information on the wikipedia pages for AVL tree and Tree rotation.  You can find links to these pages in section 4. The tree rotation page on wikipedia is lacking, I feel.  The AVL tree page needs work as well, but this page is hurting bad
l
y, and at some point in the future, I will likely integrate most of this document into that page. This document covers both types of rotations, and all 4 applications of them.  There is also a small section on deciding which rotations to use in different 
situations.
\par 
\par 
\par }{\rtlch\fcs1 \af1\afs36 \ltrch\fcs0 \f1\fs36\insrsid9191485 1. Rotations: How they work}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par A tree rotation can be an imtimidating concept at first.  You end up in a situation where you're juggling nodes, and these nodes have trees attached to them, and it can all become confusing very fast.  I find it hel
ps to block out what's going on with any of the subtrees which are attached to the nodes you're fumbling with, but that can be hard.
\par 
\par }{\rtlch\fcs1 \ab\af1\afs20 \ltrch\fcs0 \b\f1\fs20\insrsid9191485 Left Rotation (LL)
\par }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par Imagine we have this situation:
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-1
\par a
\par  \\
\par   b
\par    \\
\par     c}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par To fix this, we must perform a left rotation, rooted at A.  This is done in the following steps:
\par 
\par b becomes the new root.
\par a takes ownership of b's left child as its right child, or in this case, null.
\par b takes ownership of a as its left child.
\par 
\par The tree now looks like this:
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-2
\par   b
\par  / \\
\par a   c
\par 
\par }{\rtlch\fcs1 \ab\af1\afs20 \ltrch\fcs0 \b\f1\fs20\insrsid9191485 Right Rotation (RR)}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par A right rotation is a mirror of the left rotation operation described above.  Imagine we have this situation:
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-3
\par     c
\par    /
\par   b
\par  /
\par a}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par To fix this, we will perform a single right rotation, rooted at C.  This is done in the following steps:
\par 
\par b becomes the new root.
\par c takes ownership of b's right child, as its left child. In this case, that value is null.
\par b takes ownership of c, as it's right child.
\par 
\par The resulting tree:
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-4
\par   b
\par  / \\
\par a   c}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par }{\rtlch\fcs1 \ab\af1\afs20 \ltrch\fcs0 \b\f1\fs20\insrsid9191485 
\par Left-Right Rotation (LR) or "Double left"
\par }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par Sometimes a single left rotation is not sufficient to balance an unbalanced tree.  Take this situation:
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-5
\par a
\par  \\
\par   c}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par Perfect. It's balanced.  Let's insert 'b'.
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-6
\par a
\par  \\
\par   c
\par  / 
\par b}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par 
\par Our initial reaction here is to do a single left rotation.  Let's try that.
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-7
\par   c
\par  /
\par a
\par  \\
\par   b}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par Our left rotation has completed, and we're stuck in the same situation. If we were to do a single right rotation in this situation, we would be right back where we started.  What's causing this?  }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 
\f1\fs20\cf6\insrsid9191485\charrsid14842497 The answer is that this is a result of the right subtree having a negative balance. In other words, because the right subtree was left heavy, our rotation was not sufficient.  }{\rtlch\fcs1 \af1\afs20 
\ltrch\fcs0 \f1\fs20\insrsid9191485 What can we do?  The answer is to perf}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid16145397 orm a right rotation on the right}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
 subtree. Read that again. We will perform a right rotation on the }{\rtlch\fcs1 \ai\af1\afs20 \ltrch\fcs0 \i\f1\fs20\insrsid16145397 right}{\rtlch\fcs1 \ai\af1\afs20 \ltrch\fcs0 \i\f1\fs20\insrsid9191485  subtree}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 
\f1\fs20\insrsid9191485 .  We are not rotating on our current root. We are rotating on our right child.  Think of our right subtree, isolated from our main tree, and perform a right rotation on it:
\par 
\par Before:
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-8
\par   c
\par  /
\par b
\par }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par After:
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-9
\par b
\par  \\
\par   c}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par After performing a rotation on our right subtree, we have prepared our root to be rotated left.  Here is our tree now:
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-10
\par a
\par  \\
\par   b
\par    \\
\par     c
\par }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par Looks like we're ready for a left rotation.  Let's do that:
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-11
\par   b
\par  / \\
\par a   c}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par Voila. Problem solved.  
\par 
\par }{\rtlch\fcs1 \ab\af1\afs20 \ltrch\fcs0 \b\f1\fs20\insrsid9191485 
\par }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par }{\rtlch\fcs1 \ab\af1\afs20 \ltrch\fcs0 \b\f1\fs20\insrsid9191485 Right-Left Rotiation (RL) or "Double right"
\par }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par A double right rotation, or right-left rotation, or simply RL, is a rotation that must be performed when attempting to balance a tree which has a left subtree, that is right heavy.  This is a mirror operation
 of what was illustrated in the section on Left-Right Rotations, or double left rotations. Let's look at an example of a situation where we need to perform a Right-Left rotation.
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-12
\par   c
\par  /
\par a
\par  \\
\par   b}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par In this situation, we have a tree that is unbal
anced.  The left subtree has a height of 2, and the right subtree has a height of 0. This makes the balance factor of our root node, c, equal to -2.  What do we do? Some kind of right rotation is clearly necessary, but a single right rotation will not sol
ve our problem. Let's try it:
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-13
\par a
\par  \\
\par   c
\par  /
\par b}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par Looks like that didn't work.  Now we have a tree that has a balance of 2. It would appear that we did not accomplish much.  That is true. What do we do?  Well, let's go back to the original tree, before we did our pointless right rotation:
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-14
\par   c
\par  /
\par a
\par  \\
\par   b}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par The reason our right rotation did not work, is because the left subtree, or 'a', has a positive balance factor, and is thus right heavy.  Performing a right rotation on a tree that has a left subtree that is right heavy will result in the pro
blem we just witnessed.  What do we do?  The answer is to make our left subtree left-heavy.  We do this by performing a left rotation our left subtree.  Doing so leaves us with this situation:
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-15
\par     c
\par    /
\par   b
\par  /
\par a}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par 
\par This is a tree which can now be balanced using a single right rotation.  We can now perform our right rotation rooted at C. The result:
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 1-16
\par   b
\par  / \\
\par a   c}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par Balance at last.
\par 
\par 
\par }{\rtlch\fcs1 \af1\afs36 \ltrch\fcs0 \f1\fs36\insrsid9191485 2. Rotations, When to Use Them and Why}{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par How to decide when you need a tree rotation is usually easy, but determining which type of rotation you need requires a little thought.
\par 
\par A tree rotation is necessary when you have inserted or deleted a node which leaves the tree in an unbalanced state.  An
 unbalanced state is defined as a state in which any subtree has a balance factor of greater than 1, or less than -1.  That is, any tree with a difference between the heights of its two subtrees greater than 1, is considered unbalanced.
\par 
\par This is a balanced tree:
\par 
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 2-1
\par   1
\par  / \\
\par 2   3
\par }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par This is an unbalanced tree:
\par 
\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 Figure 2-2
\par 1
\par  \\
\par   2
\par    \\
\par     3
\par }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par This tree is considered unbalanced be
cause the root node has a balance factor of 2.  That is, the right subtree of 1 has a height of 2, and the height of 1's left subtree is 0.  Remember that balance factor of a tree with a left subtree A and a right subtree B is
\par 
\par B - A
\par 
\par Simple. 
\par 
\par In figure 2
-2, we see that the tree has a balance of 2.  This means that the tree is considered "right heavy".  We can correct this by performing what is called a "left rotation".  How we determine which rotation to use follows a few basic rules.  See psuedo code:

\par 
\par }{\rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\insrsid9191485 IF tree is right heavy
\par \{
\par   IF tree's right subtree is left heavy
\par   \{
\par      Perform Double Left rotation 
\par   \}
\par   ELSE
\par   \{
\par      Perform Single Left rotation
\par   \}
\par \}
\par ELSE IF tree is left heavy
\par \{
\par   IF tree's left subtree is right heavy
\par   \{
\par      Perform Double Right rotation
\par   \}
\par   ELSE
\par   \{
\par      Perform Single Right rotation
\par   \}
\par \}
\par }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par 
\par As you can see, there is a situation where we need to perform a "double rotation". A single rotat
ion in the situations described in the pseudo code leave the tree in an unbalanced state.  Follow these rules, and you should be able to balance an AVL tree following an insert or delete every time.
\par 
\par 
\par }{\rtlch\fcs1 \af1\afs36 \ltrch\fcs0 \f1\fs36\insrsid14694867 3. Summary}{\rtlch\fcs1 \af1\afs36 \ltrch\fcs0 \f1\fs36\insrsid9191485 
\par }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 It\rquote s important to understand that the exampl
es above were on very small trees to keep the concepts clear.  In theory, however, if you develop an application which uses AVL trees, programming for the situations shown above while using the rules provided should scale just fine. 
\par 
\par If you have comments, questions or criticisms, feel free to e-mail me at }{\field{\*\fldinst {\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 HYPERLINK "mailto:castorvx@gmail.com" }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 
\f1\fs20\insrsid9271887\charrsid14694867 {\*\datafield 00d0c9ea79f9bace118c8200aa004ba90b0200000003000000e0c9ea79f9bace118c8200aa004ba90b340000006d00610069006c0074006f003a0063006100730074006f00720076007800400067006d00610069006c002e0063006f006d0000000000}}
}{\fldrslt {\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\ul\cf2\insrsid9191485 castorvx@gmail.com}}}\sectd \linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par 
\par }{\rtlch\fcs1 \af1\afs36 \ltrch\fcs0 \f1\fs36\insrsid9191485 4. Further {\*\xmlopen\xmlns2{\factoidname place}}{\*\xmlopen\xmlns2{\factoidname City}}Reading{\*\xmlclose}{\*\xmlclose}
\par }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 - Tree rotation page on Wikipedia, }{\field{\*\fldinst {\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485  HYPERLINK "http://en.wikipedia.org/wiki/Tree_rotation" }{\rtlch\fcs1 
\af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9271887\charrsid9191485 {\*\datafield 
00d0c9ea79f9bace118c8200aa004ba90b0200000003000000e0c9ea79f9bace118c8200aa004ba90b5600000068007400740070003a002f002f0065006e002e00770069006b006900700065006400690061002e006f00720067002f00770069006b0069002f0054007200650065005f0072006f0074006100740069006f00
6e0000000072}}}{\fldrslt {\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \cs15\f1\fs20\ul\cf2\insrsid9191485\charrsid9191485 http://en.wikipedia.org/wiki/Tree_rotation}}}\sectd \linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 

\par - AVL tree page on Wikipedia, }{\field{\*\fldinst {\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485  HYPERLINK "http://en.wikipedia.org/wiki/AVL_tree" }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9271887\charrsid9191485 {\*\datafield 
00d0c9ea79f9bace118c8200aa004ba90b0200000003000000e0c9ea79f9bace118c8200aa004ba90b4c00000068007400740070003a002f002f0065006e002e00770069006b006900700065006400690061002e006f00720067002f00770069006b0069002f00410056004c005f00740072006500650000000000}}
}{\fldrslt {\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \cs15\f1\fs20\ul\cf2\insrsid9191485\charrsid9191485 http://en.wikipedia.org/wiki/AVL_tree}}}\sectd \linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par - Animated AVL Tree Java applet, }{\field{\*\fldinst {\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485  HYPERLINK "http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm" }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 
\f1\fs20\insrsid9271887\charrsid9191485 {\*\datafield 
00d0c9ea79f9bace118c8200aa004ba90b0200000003000000e0c9ea79f9bace118c8200aa004ba90b8a00000068007400740070003a002f002f00770065006200700061006700650073002e0075006c006c002e00650073002f00750073006500720073002f006a00720069006500720061002f0044006f00630065006e00
6300690061002f00410056004c002f00410056004c002000740072006500650020006100700070006c00650074002e00680074006d0000000000}}}{\fldrslt {\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \cs15\f1\fs20\ul\cf2\insrsid9191485\charrsid9191485 h
ttp://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm}}}\sectd \linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par - AVL Trees: Tutorial and C++ Implementation, }{\field{\*\fldinst {\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485  HYPERLINK "http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html" }{\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 
\f1\fs20\insrsid9271887\charrsid9191485 {\*\datafield 
00d0c9ea79f9bace118c8200aa004ba90b0200000003000000e0c9ea79f9bace118c8200aa004ba90b8600000068007400740070003a002f002f007700770077002e0063006d00630072006f007300730072006f006100640073002e0063006f006d002f0062007200610064006100700070002f006600740070002f007300
720063002f006c006900620073002f0043002b002b002f00410076006c00540072006500650073002e00680074006d006c0000000000}}}{\fldrslt {\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \cs15\f1\fs20\ul\cf2\insrsid9191485\charrsid9191485 
http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html}}}\sectd \linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af1\afs20 \ltrch\fcs0 \f1\fs20\insrsid9191485 
\par 
\par 
\par }}